package algorithms.question.class10;

import common.util.MyUtil;

/**
 * https://leetcode-cn.com/problems/jump-game-ii/
 *
 * @author guichang
 * @date 2021/8/7
 */

@SuppressWarnings("all")
public class Code1_跳跃游戏 {

    public static void main(String[] args) {
        int[] arr = MyUtil.createArray(2, 3, 1, 1, 4);
        MyUtil.print(jump(arr));

    }

    public static int jump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int step = 0; // 当前走的步数
        int curr = 0; // 当前走了step步之后最远走到curr步
        int next = nums[0]; // 多走一步之后最远能走到哪里
        int N = nums.length;
        for (int i = 1; i < N; i++) {
            // 当前位置大于curr表示要走一步了
            if (curr < i) {
                step++;
                curr = next;
                next = 0;
            }
            next = Math.max(next, i + nums[i]);
            // 提前走完
            if(curr >= N-1) {
                return step;
            }
            if(next >= N-1) {
                return step + 1;
            }
        }
        return step;
    }

}